package main

import "fmt"
// 给定一个整数 n, 返回从 1 到 n 的字典顺序。
// 例如，
// 给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
// 请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
func dfs(res *[]int, i int, n int){
	if i > n{
		return
	}

	*res = append(*res, i)
	for j :=0; j <= 9; j++{
		dfs(res, 10 * i + j, n)
	}
}

func dicsort(n int){
	res := []int{}
	for i := 1; i <= 9; i++{
		dfs(&res, i, n)
	}
	fmt.Println(res)
}



func main(){
	dicsort(13)
}
